package com.javaDemo.ti;

/**
 * 单词搜索
 * 
 * @author csy
 * @date 2021/3/12 09:34
 * @description 在二维字符网格中搜索单词
 * 
 *              解题思路：
 *              1. 使用回溯法（DFS + 回溯）遍历二维网格
 *              2. 从每个格子开始，向四个方向搜索
 *              3. 使用visited数组标记已访问的格子
 *              4. 当找到完整单词时返回true
 * 
 *              时间复杂度：O(M*N*4^L)，其中M和N是网格的长宽，L是单词长度
 *              空间复杂度：O(M*N)，主要是visited数组的开销
 * 
 *              参考：https://leetcode-cn.com/problems/word-search/
 */
public class WordSearch {
    // 四个方向的移动：上、左、右、下
    private static final int[][] DIRECTIONS = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

    // 记录格子是否被访问过
    private static boolean[][] visited;

    // 是否找到目标单词
    private static boolean found = false;

    /**
     * 在字符网格中搜索单词
     *
     * @param board 字符网格
     * @param word  要搜索的单词
     * @return 是否找到单词
     */
    public static boolean search(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null || word.isEmpty()) {
            return false;
        }

        int rows = board.length;
        int cols = board[0].length;
        visited = new boolean[rows][cols];
        char[] wordChars = word.toCharArray();

        // 从每个格子开始尝试搜索
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果第一个字符匹配，开始回溯搜索
                if (board[i][j] == wordChars[0]) {
                    backtrack(board, wordChars, 1, i, j);
                    if (found) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 回溯搜索
     *
     * @param board   字符网格
     * @param word    目标单词的字符数组
     * @param current 当前要匹配的字符位置
     * @param row     当前行
     * @param col     当前列
     */
    private static void backtrack(char[][] board, char[] word, int current, int row, int col) {
        // 如果已经找到单词，直接返回
        if (found) {
            return;
        }

        // 如果已经匹配完所有字符，标记为找到
        if (current == word.length) {
            found = true;
            return;
        }

        // 标记当前格子为已访问
        visited[row][col] = true;

        // 向四个方向搜索
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];

            // 如果新位置有效且未访问过且字符匹配，继续搜索
            if (isValid(newRow, newCol, board) &&
                    !visited[newRow][newCol] &&
                    board[newRow][newCol] == word[current]) {
                backtrack(board, word, current + 1, newRow, newCol);
            }
        }

        // 回溯，取消当前格子的访问标记
        visited[row][col] = false;
    }

    /**
     * 检查坐标是否在网格范围内
     *
     * @param row   行坐标
     * @param col   列坐标
     * @param board 字符网格
     * @return 坐标是否有效
     */
    private static boolean isValid(int row, int col, char[][] board) {
        return row >= 0 && row < board.length && col >= 0 && col < board[0].length;
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试用例
        char[][] board = {
                { 'A', 'B', 'C', 'E' },
                { 'S', 'F', 'C', 'S' },
                { 'A', 'D', 'E', 'E' }
        };
        String word = "ABCCED";

        boolean result = search(board, word);
        System.out.printf("在网格中%s找到单词 \"%s\"%n",
                result ? "成功" : "未", word);
    }
}